package leetcode;

import java.util.HashMap;
import java.util.LinkedList;

/*
运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制。
它应该支持以下操作： 获取数据 get 和 写入数据 put 。

若 get 的键在缓存里面返回值，否则返回 -1
若 put 的时候，不存在该键，则put进去，容量满了则应该先删除最近最少使用的
 */
public class Test146LRU缓存机制 {

    /*
    借助Java里面已经实现的 HashMap 以及 LinkedList 完成算法
     */

    static class LRUCache {

        public final int capacity;
        public LinkedList<Integer> list = new LinkedList<>();
        public HashMap<Integer, Integer> map = new HashMap<>();

        public LRUCache(int capacity) {
            this.capacity = capacity;
        }

        public int get(int key) {
            // 没有键就返回 -1
            if (!map.containsKey(key)) {
                return -1;
            }
            // 有的话先改变 LRU 状态
            moveToFirst(key);
            // 再返回数据
            return map.get(key);
        }

        private void moveToFirst(int key) {
            // 首先删除链表里面的这个键
            if (list.size() > 1)
                list.remove(Integer.valueOf(key));
            // 然后把这个键放到首部
            list.addFirst(key);
        }

        public void put(int key, int value) {
            // 若 map 里面没有该键，则尝试放入
            if (!map.containsKey(key)) {
                if (map.size() >= capacity) { // 应为下标从0开始的，这里要用=号
                    // 缓存容量满了，删除链表最后一个数据（也就是最近很少使用的数据）
                    // 移除最有一个后要接着添加
                    map.remove(list.removeLast());
                }
                // 没满就添加进去
                list.addFirst(key);
                map.put(key, value);
            } else {
                // map 里面已经有了key，先更改链表顺序
                moveToFirst(key);
                // 再修改map的内容
                map.put(key, value);
            }
        }


        public static void main(String[] args) {
            LRUCache cache = new LRUCache(2);
            cache.put(2, 1);
            cache.put(2, 2);
            cache.get(2);
            cache.put(1, 1);
            cache.put(4, 1);
            cache.get(2);
            System.out.println();
        }
    }
}
